#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

//134.加油站
int canCompleteCircuit(vector<int>& gas, vector<int>& cost){
    int n = gas.size();
    //枚举所有的起始位置
    for (int i = 0; i < n; i++){
        //净收益
        int rest = 0;
        //步数
        int step=0;
        for (; step < n; step++){
            //下一步的位置
            int index = (i + step) % n;
            rest = rest + gas[index] - cost[index];
            if(rest<0){
                break;
            }
        }
        if(rest>=0){
            return i;
        }
        //这里是贪心的思想，从小于0的下一个位置开始从新作为起始位置
        i += step;
    }

    return -1;
}

//738.单调递增的数字
int monotoneIncreasingDigits(int n){
    //先将数字转化成字符串形式
    string s = to_string(n);

    //找到第一个递减的位置
    int m = s.size();
    int i = 0;
    while(i+1<m&&s[i]<=s[i+1]){
        i++;
    }

    //如果没有找到递减位置，直接返回当前数字
    if(i+1==m){
        return n;
    }

    //找到递减位置，向前找到最左侧相同值的位置
    while(i-1>=0&&s[i]==s[i-1]){
        i--;
    }

    //第一个相同值-1，其余位置全部修改成9
    s[i] = s[i] - 1;
    for (int j = i + 1; j < m; j++){
        s[j] = '9';
    }

    //修改完后转化成数字返回
    return stoi(s);
}

//991.坏了的计算器
int brokenCalc(int startValue, int target){
    //正难则反思想，目标值除法或者加法变成初始值

    int ret = 0;
    while(target!=startValue){
        //如果目标值小于初始值，全选加法
        if(target<startValue){
            ret += (startValue - target);
            break;
        }
        //如果大于
        else{
            //如果目标值是奇数，选加法
            if(target%2==1){
                target += 1;
            }
            //如果是偶数，优先选除法
            else{
                target /= 2;
            }
            ret++;
        }
    }
    
    return ret;
}

//56.合并区间
vector<vector<int>> merge(vector<vector<int>>& intervals){
    //先将所有区间按照左端点排序
    sort(intervals.begin(), intervals.end());

    int left = 0, right = 0;
    vector<vector<int>> ret;
    for (int i = 0; i < intervals.size(); i++){
        int a = intervals[i][0], b = intervals[i][1];
        if(i==0){
            left = a, right = b;
        }

        //如果下一个区间的左端点小于上一个区间的右端点，左端点不变，右端点取最大的
        if(a<=right){
            right = max(b, right);
        }
        //如果下一个区间的左端点大于上一个区间的右端点，说明没有交集
        else{
            ret.push_back({left, right});
            //更新做右端点
            left = a, right = b;
        }

        //遍历到最后一个区间，直接存放到数组中
        if(i==intervals.size()-1){
            ret.push_back({left, right});
        }
    }

    return ret;
}

int main(){
    int ret=brokenCalc(5, 8);
    return 0;
}